package cn.xiaolang.function.data_structure;

import lombok.Data;

/**
 * 剑指 Offer 26. 树的子结构 https://leetcode.cn/problems/shu-de-zi-jie-gou-lcof/
 * 输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
 * B是A的子结构， 即 A中有出现和B相同的结构和节点值。 （TODO）
 * <p>
 * 例如:
 * <p>
 * 给定的树 A:
 * 3
 * / \
 * 4   5
 * / \
 * 1   2
 *
 * <p>
 * 给定的树 B：
 * 4
 * /
 * 1
 * 返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。
 * <p>
 * 示例 1：
 * 输入：A = [1,2,3], B = [3,1]
 * 输出：false
 * <p>
 * 示例 2：
 * 输入：A = [3,4,5,1,2], B = [4,1]
 * 输出：true
 * <p>
 * 限制：
 * 0 <= 节点个数 <= 10000
 */
public class No24IsSubStructure {

    public static void main(String[] args) {
        No24IsSubStructure algorithm = new No24IsSubStructure();
        TreeNode a = new TreeNode(3);
        TreeNode four = new TreeNode(4);
        a.setLeft(four);
        a.setRight(new TreeNode(5));
        four.setLeft(new TreeNode(1));
        four.setRight(new TreeNode(2));

        TreeNode b = new TreeNode(4);
        b.setLeft(new TreeNode(1));

        boolean subStructure = algorithm.isSubStructure(a, b);
        System.out.println(subStructure);

    }


    public boolean isSubStructure(TreeNode A, TreeNode B) {

        return true;
    }

    @Data
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}
